package easy;

public class Solution_1051 {

    public int heightChecker(int[] heights) {
        int[] copy = new int[101];
        for (int i = 0; i < heights.length; i++) {
            copy[heights[i]]++;
        }
        int count = 0;
        for (int i = 1, index = 0; i < copy.length;) {
            if (copy[i]>0) {
                if (heights[index] != i) {
                    count++;
                }
                index++;
                copy[i]--;
            } else {
                i++;
            }
        }
        return count;
    }

    /*public int heightChecker(int[] heights) {
        int[] copy = new int[heights.length];
        System.arraycopy(heights, 0, copy, 0, heights.length);
        Arrays.sort(copy);
        int count = 0;
        for (int i = 0; i < copy.length; i++) {
            if (heights[i] != copy[i]) {
                count++;
            }
        }
        return count;
    }*/

    public static void main(String[] args) {
        Solution_1051 model = new Solution_1051();
        System.out.println(model.heightChecker(new int[]{1, 1, 4, 2, 1, 3}));
        System.out.println(model.heightChecker(new int[]{5, 1, 2, 3, 4}));
        System.out.println(model.heightChecker(new int[]{1, 2, 3, 4, 5}));
    }
}
